// 09-排序3 Insertion or Heap Sort
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100

#define ElementType int

/* 基础工具(swap.c) =======================================*/

void swap(ElementType *a, ElementType *b) {
    ElementType t;
    t = *a;
    *a = *b;
    *b = t;
}

int comparator(ElementType a, ElementType b) {
    if (a > b) {
        return 1;
    } else if (a < b) {
        return -1;
    } else {
        return 0;
    }
}

// 打印空格分隔的，结尾无空格的数组
void printArray(int a[], int n) {
    if (n < 1 || a == NULL) {
        return;
    }
    printf("%d", *a++);
    for (int i=1; i<n; i++) {
        printf(" %d", *a++);
    }
}

void inputArray(int a[], int n) {
    for (int i=0; i<n; i++, a++) {
        scanf("%d", a);
    }
}

/* Insertion =====================================*/
// 从第 P 趟开始继续排
void insertion_Sort_Pass(ElementType a[], int p, int length) {
    ElementType tmp = a[p]; // 下一个待排序的数
    int i;
    for (i=p; i > 0 && comparator(a[i-1], tmp) > 0; i--) {
        a[i] = a[i-1]; // 移出空位
    }
    // 插入
    a[i] = tmp;
}

/* Heap sort =========================================*/
void percDown(ElementType a[], int startIdx, int length) {
    int parent, child;
    // 取出 startIdx 处存放的值
    ElementType temp = a[startIdx];
    // 向下（左右儿子）找可以正确存放 temp 的合适位置
    for (parent = startIdx; parent*2+1 < length; parent = child /* 顺着调整过的儿子节点继续向下 */) {
        child = parent*2+1;
        if ((child != length - 1) && comparator(a[child], a[child+1]) < 0) {
            // 有右儿子，且右儿子比较大
            child++; // 指向右儿子
        }
        if (comparator(temp, a[child]) >= 0) {
            // temp 比它的左右儿子都大，即找到了合适位置，不用再往下找了
            break;
        }
        // 把更大的子节点复制到父节点位置，即把大的数往上调
        a[parent] = a[child];
    }
    a[parent] = temp;
}

/* current =======================================*/
// 检查是否插入排序
// 前p个有序，后n-p个和原始序列一样
int isInsertion(int *base, int *sorted, int n) {
    int p;
    for (p=0; p<n; p++) {
        if (sorted[p] > sorted[p+1]) {
            break;
        }
    }
    int left;
    for (left=p+1; left < n; left++) {
        if (base[left] != sorted[left]) {
            break;
        }
    }
    if (left == n) {
        // 是insertion,返回执行了几次
        return p;
    } else {
        return 0;
    }
}

/* Heap Sort =========================================*/
// 找到堆长度
int getLeftLength(int *sorted, int n) {
    int i;
    for (i=n-1; i>0; i--) {
        // 已排好序的元素一定大于顶部元素
        if (comparator(sorted[i], sorted[0]) < 0) {
            break;
        }
    }
    return i+1;
}

int main() {
    // 原始
    int base[MaxSize];
    // 排好序的
    int sorted[MaxSize];
    
    int n;
    scanf("%d", &n);

    inputArray(base, n);
    inputArray(sorted, n);

    int p = isInsertion(base, sorted, n);
    if (p != 0) {
        printf("Insertion Sort\n");
        insertion_Sort_Pass(sorted, p+1, n);
        printArray(sorted, n);
    } else {
        printf("Heap Sort\n");
        int len = getLeftLength(sorted, n);
        // printf("len = %d\n", len);
        swap(&sorted[0], &sorted[len-1]);
        percDown(sorted, 0, len-1);
        // merge_pass(sorted, base, n, step);
        printArray(sorted, n);
    }

    return 0;
}
